﻿using System;
using System.Collections.Generic;
using System.Text;

namespace 算法
{
    
    /// <summary>
    /// 有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
    ///现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 
    ///这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
    ///求所能获得硬币的最大数量。
    /// </summary>
    public  class _312
    {
        public int maxCoin;
        public int MaxCoins(int[] nums)
        {
            int lengh = nums.Length;
            GetMaxCoins(nums, 0, lengh, 0);
            return maxCoin;
        }
        /// <summary>
        ///  y：递归层级，即currentLevel,
        ///length：数组长度，防止每层都计算一次， 
        // beforeCoins：之前所有层获得的金币和，即currentCoin
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public void GetMaxCoins(int[] nums, int y, int length, int beforeCoins)
        {
            if (y == length)//当前已经到最后一层了怕判断最大的值跟当前的值谁大
            {
                if (beforeCoins> maxCoin)
                {
                    maxCoin = beforeCoins;
                }
            }
            for (int i = 0; i < length; i++)//当前层炸破i气球
            {
                if (nums[i]==-1)
                    continue;
                int temp = nums[i];
                nums[i] = -1;
                int after = i - 1;
                int afterNum = 0;
                //判断左边的气球
                while (after>-1&&nums[after]==-1)//把已经挑取过的排除
                {
                    after--;
                }
                if (after==-1)
                {
                    afterNum = 1;
                }
                else
                {
                    afterNum = nums[after];
                }
                //判断右边的气球
                int right = i + 1;
                int rightNum = 0;
                while (right<length&&nums[right]==-1)
                {
                    right++;
                }
                if (right==length)
                {
                    rightNum = 1;
                }
                else
                {
                    rightNum = nums[right];
                }
                int curNum = afterNum * temp * rightNum;
                GetMaxCoins(nums, y + 1,length, curNum+ beforeCoins);
                nums[i] =temp;//还原气球
            }
        }
    }
}
